package com.gxc.tree;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 */
public class PathSum {

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;

          TreeNode() {
          }

          TreeNode(int val) {
              this.val = val;
          }

          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }


    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix  = new HashMap<>();
        prefix .put(0l, 1);
        return dfs(root, prefix, 0l, targetSum);
    }

    private int dfs(TreeNode root, Map<Long, Integer> prefix, Long cur, int targetSum) {
        if (root == null) return 0;

        int ret = 0;
        cur += root.val;
        ret += prefix.getOrDefault(cur - targetSum, 0);
        prefix.put(cur, prefix.getOrDefault(cur, 0) +1);
        ret += dfs(root.left, prefix, cur, targetSum);
        ret += dfs(root.right, prefix, cur, targetSum);
        //回滚
        prefix.put(cur, prefix.getOrDefault(cur, 0) -1);
        return ret;
    }
}
